package offer2

import (
	"math"
)

/**
原题链接:
https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/

B站 帅地玩编程
剑指offer 60.n个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

一个骰子 1-6
两个骰子 2-12
...
n个骰子  n-6n

示例1
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

示例2
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

提示
1 <= n <= 11
*/

/**
暴力法:
组合有6n种组合, 那么点数范围s = [n:6n]
对于每一个点数, 看有多少种组合是满足某一个点数的

比如说: 对于点数8, 满足它的情况有k种, 那么算概率直接用 k/6n即可

思路：动态规划
n个骰子，那么点数情况范围就是 s=[n,6n]

对于某个点数，要看有多少种组合满足
假设对于满足点数8的情况有k种， 那么计算点数8的概率就是  k/6^n


筛子的个数是n个，点数范围为[n,6n]
1. dp数组含义:
	dp[i][j]: 表示当骰子个数为i，点数为j的时候，此时它的组合有多少种

2. 递推公式
	求某个点数的几率，即 dp[i][j] / 6^n
	因为i比i-1多了一个骰子, j点数是从上一轮+1,+2...+6获取到的, 所以几率等于上一轮概率相加
	dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][j-6]

3. 初始化
	那么当只有一个骰子的时候:
	dp[1][1]=1, dp[1][2]=1, dp[1][3]=1, dp[1][4]=1, dp[1][5]=1, dp[1][6]=1
*/

func statisticsProbability(num int) []float64 {
	dp := make([][]int, num+1) // 创建二维dp数组点数从1开始, 长度记得+1
	for i := range dp {
		dp[i] = make([]int, 6*num+1) //点数从1开始, 长度记得+1
	}

	for i := 1; i <= 6; i++ { // 初始化，当只有一个骰子的时候的情况
		dp[1][i] = 1
	}

	for i := 2; i <= num; i++ { // 依次从第二个骰子开始填充dp数组 骰子个数逐渐增减
		for j := i; j <= 6*i; j++ { // 点数的取值范围，是从i个骰子开始，到6i个骰子结束
			for k := 1; k <= 6; k++ { // 增加了一个骰子，点数比上一轮骰子的点数依次少1,2,3,4,5,6个
				if j < k {
					break // 点数j不能比k小，不然没意义
				}
				dp[i][j] += dp[i-1][j-k]
			}
		}
	}

	res := make([]float64, 5*num+1) // 结果数组，点数取值范围[骰子个数,6*骰子个数]，所以结果数组的个数为5*骰子个数+1
	index := 0
	sum := math.Pow(6, float64(num)) // 一共有多少种组合 6的几次方

	for i := num; i <= 6*num; i++ { // 分别跟组合总数计算概率，填充数组
		res[index] = float64(dp[num][i]) / sum
		index++
	}

	return res
}
